In a multi-processor system, it is frequently desirable to build queues, or first-in-first-out (FIFO) buffers, in memory. A queue is a data structure with FIFO properties where agents push elements onto the queue (writes) and pop elements off of the queue (reads). This in normally accomplished by allocating storage for the queue elements, and separately allocating storage for the queue state which includes read and write pointers, and any other desired information.
When software wants to read an element from the queue, or write an element to the queue, it first must ensure that it has exclusive and atomic control of the queue element and queue state storage. Then it must update the queue state and access the queue element to perform its operation. Finally, the memory that controls the ownership of the shared memory block must be updated to indicate that the operation is complete. Since there are usually multiple processors using a queue, this requires some forms of data locking of the queue states to ensure that the access to the queue states and the access to the queue element are atomic and consistent. Data locking, and particularly contention over the lock state memory locations, is often a performance-limiting operation in multi-processor systems. In particular, if there are both multiple producers and multiple consumers of queue data, the performance implications can be severe.